`
https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/
`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function (A, B) {
  if (A === null || B === null) {
    return false
  }
  // 对于树 A 中的一个节点：
  // 1. 如果 A.val == B.val，则 A 可以作为根节点尝试去匹配树 B
  if (A.val === B.val && compareTree(A, B)) {
    return true
  }
  return isSubStructure(A.left, B) || isSubStructure(A.right, B)
};

// 这个函数用「分解问题」的思路理解
// 定义：输入两个根节点，返回从 rootA 开始是否可以完全匹配 rootB 树上的所有节点
var compareTree = function (rootA, rootB) {
  // base case
  if (rootB === null) {
    return true;
  }
  if (rootB !== null && rootA === null) {
    return false;
  }
  if (rootA.val !== rootB.val) {
    return false;
  }

  // rootA 的值和 rootB 的值匹配完成，去匹配子树的节点
  return compareTree(rootA.left, rootB.left) && compareTree(rootA.right, rootB.right);
}